#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include<cmath>

using namespace std;
/*HJJ QQ479287006
 *给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

 

示例 1:

输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
示例 2:

输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/divide-two-integers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */

/**
    * 解题思路：这题是除法，所以先普及下除法术语
    * 商，公式是：(被除数-余数)÷除数=商，记作：被除数÷除数=商...余数，是一种数学术语。
    * 在一个除法算式里，被除数、余数、除数和商的关系为：(被除数-余数)÷除数=商，记作：被除数÷除数=商...余数，
    * 进而推导得出：商×除数+余数=被除数。
    *
    * 要求商，我们首先想到的是减法，能被减多少次，那么商就为多少，但是明显减法的效率太低
    *
    * 那么我们可以用位移法，因为计算机在做位移时效率特别高，向左移1相当于乘以2，向右位移1相当于除以2
    *
    * 我们可以把一个dividend（被除数）先除以2^n，n最初为31，不断减小n去试探,当某个n满足dividend/2^n>=divisor时，
    *
    * 表示我们找到了一个足够大的数，这个数*divisor是不大于dividend的，所以我们就可以减去2^n个divisor，以此类推
    *
    * 我们可以以100/3为例
    *
    * 2^n是1，2，4，8...2^31这种数，当n为31时，这个数特别大，100/2^n是一个很小的数，肯定是小于3的，所以循环下来，
    *
    * 当n=5时，100/32=3, 刚好是大于等于3的，这时我们将100-32*3=4，也就是减去了32个3，接下来我们再处理4，同样手法可以再减去一个3
    *
    * 所以一共是减去了33个3，所以商就是33
    *
    * 这其中得处理一些特殊的数，比如divisor是不能为0的，Integer.MIN_VALUE和Integer.MAX_VALUE
    *
    */

//自己想的时候肯定是 dividend - divisor 寻求一个个数 但是如果数字很大则循环很多
//对于那个指数的想法是 dividend -divisor*(2*n次方) 寻找一个n的中间值
// 例如100/3 =33 结果
// 100/2^n>=3(被除数)  --->  100/2^5=3.33   因此为（）        此时使用100-3*2^5= 3.33 循环减去3就行
//这个题我这边出现了一定的问题 abs 无法正确值
int divide(int dividend, int divisor) {

    if (dividend == INT_MIN && divisor == -1)
        return INT_MAX;

    if (dividend == 0)
        return 0;

    long a = ((long) dividend);
    long dividendTemp = abs(a);
    long divisorTemp = abs((long) divisor);;


    if (dividendTemp < divisorTemp)
        return 0;


    int ret = 0;
    int i;
    for (i = 31; i >= 0; --i) {

        int p = dividendTemp >> i;
        if (p >= divisorTemp) {
            int pLeft = dividendTemp - (divisorTemp << i);//剩余的数 就是 4
            while (pLeft >= 0) {
                pLeft -= divisorTemp;
                ret++;

            }
            if (pLeft < 0) {
                ret--;
                break;
            }

        }


    }

    int retp = (1 << i) + ret;
    if ((dividend ^ divisor) < 0)
        return -retp;


    return retp;

}